class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor(compare) {
    // 定义compare(a, b) < 0 则 a < b
    this.compare = compare;
    this.root = null;
    this.size = 0;
  }

  size() {
    return this.size;
  }
  isEmpty() {
    return this.size === 0;
  }

  /* add(data) {
    if (!this.root) {
      this.root = new Node(data);
      this.size++;
      return;
    }
    this._add(this.root, data);
  }

  _add(node, data) {
    if (this.compare(node.data, data) === 0) {
      return;
    }

    if (this.compare(data, node.data) < 0 && !node.left) {
      node.left = new Node(data);
      this.size++;
      return;
    } else if (this.compare(data, node.data) > 0 && !node.right) {
      node.right = new Node(data);
      this.size++;
      return;
    }

    if (this.compare(data, node.data) < 0) {
      this._add(node.left, data);
    } else {
      this._add(node.right, data);
    }
  } */
  add(data) {
    this.root = this._add(this.root, data);
  }

  // 含义：向以为根节点的树插入元素data，并返回根源是
  _add(node, data) {
    if (!node) {
      this.size++;
      return new Node(data);
    }

    if (this.compare(data, node.data) < 0) {
      node.left = this._add(node.left, data);
    } else if (this.compare(data, node.data) > 0) {
      node.right = this._add(node.right, data);
    }
    return node;
  }

  //
  contains(data) {
    return this._contains(this.root, data);
  }

  _contains(node, data) {
    if (!node) {
      return false;
    }
    if (node.data === data) {
      return true;
    } else if (this.compare(data, node.data) < 0) {
      return this._contains(node.left, data);
    } else {
      return this._contains(node.right, data);
    }
  }

  // 层序遍历
  levelOrder() {
    if (!this.root) {
      return;
    }
    // 使用队列实现，每次访问根节点，就依次把左右节点入队
    const arr = [];
    arr.push(this.root);
    while (arr.length) {
      const curr = arr.shift();
      console.log(curr.data);
      curr.left && arr.push(curr.left);
      curr.right && arr.push(curr.right);
    }
  }

  // 前序遍历非递归实现
  prevOrder2() {
    const arr = [];
    // 使用栈模拟实现
    arr.push(this.root);
    while (arr.length) {
      const cur = arr.pop();
      console.log(cur.data);
      if (cur.right) {
        arr.push(cur.right);
      }
      if (cur.left) {
        arr.push(cur.left);
      }
    }
  }
  // 前序遍历
  prevOrder() {
    this._prevOrder(this.root);
  }
  _prevOrder(node) {
    if (!node) {
      return;
    }
    console.log(node.data);
    this._prevOrder(node.left);
    this._prevOrder(node.right);
  }

  // 中序遍历，输出是拍好序的
  inOrder() {
    this._inOrder(this.root);
  }
  _inOrder(node) {
    if (!node) {
      return;
    }
    this._inOrder(node.left);
    console.log(node.data);
    this._inOrder(node.right);
  }

  // 后序遍历
  postOrder() {
    this._postOrder(this.root);
  }
  _postOrder(node) {
    if (!node) {
      return;
    }
    this._postOrder(node.left);
    this._postOrder(node.right);
    console.log(node.data);
  }

  // 找到最小节点
  minNode() {
    if (this.isEmpty()) {
      throw new Error('tree is empty');
    }
    return this._minNode(this.root);
  }

  _minNode(node) {
    if (!node.left) {
      return node;
    }
    return this._minNode(node.left);
  }

  // 删除最小节点
  removeMin() {
    const min = this.minNode();
    this.root = this._removeMin(this.root);
    return min.data;
  }

  // 删除以node为根节点中的最小节点，并返回根节点
  _removeMin(node) {
    if (!node.left) {
      const rightNode = node.right;
      node.right = null;
      this.size--;
      return rightNode;
    }
    node.left = this._removeMin(node.left);
    return node;
  }

  // 找到最大节点
  maxNode() {
    if (this.isEmpty()) {
      throw new Error('tree is empty');
    }
    return this._maxNode(this.root);
  }

  _maxNode(node) {
    if (!node.right) {
      return node;
    }
    return this._maxNode(node.right);
  }

  // 删除最大节点
  removeMax() {
    const max = this.maxNode();
    this.root = this._removeMax(this.root);
    return max.data;
  }

  // 删除以node为根节点中的最小节点，并返回根节点
  _removeMax(node) {
    if (!node.right) {
      const leftNode = node.left;
      node.left = null;
      this.size--;
      return leftNode;
    }
    node.right = this._removeMax(node.right);
    return node;
  }

  // 删除任意元素
  remove(data) {
    this.root = this._remove(this.root, data);
  }

  // 删除以node为根节点的daata值，并返回删除后的根节点
  _remove(node, data) {
    if (!node) {
      return null;
    }
    if (this.compare(data, node.data) < 0) {
      node.left = this._remove(node.left, data);
    } else if (this.compare(data, node.data) > 0) {
      node.right = this._remove(node.right, data);
    } else {
      if (!node.left) {
        const right = node.right;
        node.right = null;
        return right;
      }
      if (!node.right) {
        const left = node.left;
        node.left = null;
        return left;
      }
      // 都不为空
      const rightMin = this.minNode(node.right);
      rightMin.right = this._removeMin(node.right);
      rightMin.left = node.left;
      node.left = node.right = null;
      return rightMin;
    }
  }
}

var tree = new BST((a, b) => a - b);
const arr = [5, 3, 1, 4, 9, 7, 11];
/* 
      5
    3     9 
  1  4  7   11
*/
arr.forEach((data) => {
  tree.add(data);
});
// tree.prevOrder(); // 5 3 1 4 9 7 11
// tree.inOrder(); // 1 3 4 5 7 9 11
// tree.postOrder(); // 1 4 3 7 11 9 5
// tree.levelOrder(); // 5 3 9 1 4 7 11
// tree.prevOrder2(); // 5 3 1 4 9 7 11

//
var arr2 = [];
while (!tree.isEmpty()) {
  arr2.push(tree.removeMin());
}
console.log(arr2);
